#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int value;

	struct node* left;
	struct node* right;
}tree;

tree * insert (tree * root, int value)
{
	tree *node;
	if (!root) {
		node = malloc(sizeof(tree));
		node->value = value;
		node->left = node->right = NULL;
		return node;
	}

	tree *active, *prev;
	active = root;

	while (active) {

		prev = active;

		if (active->value < value)
			active = active->right;
		else if (active->value > value)
			active = active->left;
		else {
			printf ("%d element already exists\n", value);
			return root;
		}
	}

	node = malloc(sizeof(tree));
	node->value = value;
	node->left = node->right = NULL;

	if (prev->value < value)
		prev->right = node;
	else
		prev->left = node;

	return root;
}

/* Ideally we should be searching. What we do below is 
 * just a post order traversal
 */
void dfs (tree *root)
{
	if (!root)
		return;

	dfs (root->left);
	dfs (root->right);
	printf ("%d\t", root->value);

	return;
}

int main ()
{
	tree *t;

	t = insert (NULL, 4);
	t = insert (t, 2);
	t = insert (t, 9);
	t = insert (t, 1);
	t = insert (t, 3);
	t = insert (t, 5);
	t = insert (t, 12);


	dfs (t);

	return 0;
}
